<?php
	
	function subconjuntos($TablaEstadosAFN,$myAlfabeto){
		echo '<br/><br/><h2>Subconjuntos</h2>';	

		$tablaEstadosAFD = array();		
		$abededario = 'ABCDEFGHIJKLMNOPQRSTUVWXZ';
		$numEstados = 0;	
		$estadoInicialAFN = array();
		$estadoFinalAFN = NULL;
		
		//Determinar estado inicial del AFN
		foreach($TablaEstadosAFN as $estado)
			if ($estado->inicial == 1)
				$estadoInicialAFN[] = $estado->numero;

		
		//Determinar estado final del AFN
		foreach($TablaEstadosAFN as $estado)
			if ($estado->aceptacion == 1)
				$estadoFinalAFN = $estado->numero;

		
		//Agregar a la tabla de estados el estado 'A' como no marcado, que es la cerradura-E del estado inicial del AFN
		$numEstados++;
		$conjuntoEstados = cerrE($TablaEstadosAFN,$estadoInicialAFN);
		sort($conjuntoEstados);
		$estadoNuevo = new EstadoAFD($abededario[$numEstados-1],$conjuntoEstados,$myAlfabeto);
		$estadoNuevo->inicio=1;
		$tablaEstadosAFD[]=$estadoNuevo;
		
		//echo '<pre>';					
		//print_r($tablaEstadosAFD);
		//echo '</pre>';			
		
		$i=0;
		$parar = false;
		while($parar==false){
			$tablaEstadosAFD[$i]->marcado = 1;
			//echo '<br/>Marque: '.$tablaEstadosAFD[$i]->letra.'<br/><br/>';
			
			foreach($myAlfabeto as $simbolo){
				$u = cerrE($TablaEstadosAFN,mueve($TablaEstadosAFN,$tablaEstadosAFD[$i]->conjuntoEstados,$simbolo));
				sort($u);
				//echo '<br/><br/>cerrE(mueve('.$tablaEstadosAFD[$i]->letra.','.$simbolo.'))';
				//echo '<pre>';					
				//print_r($u);
				//echo '</pre>';	
				
				//comprobar que $u no pertenezca a $tablaEstadosAFD
				$noexiste = true;
				foreach($tablaEstadosAFD as $estadoAFD)
					if ($estadoAFD->conjuntoEstados == $u){
						$noexiste = false;
						$tablaEstadosAFD[$i]->transiciones[$simbolo] = $estadoAFD->letra;	
					}
				//Si no existe entoces agregarmos $u a $tablaEstadosAFD
				if ($noexiste){					
					$numEstados++;
					$estadoNuevo = new EstadoAFD($abededario[$numEstados-1],$u,$myAlfabeto);
					$tablaEstadosAFD[]=$estadoNuevo;
					$tablaEstadosAFD[$i]->transiciones[$simbolo] = $abededario[$numEstados-1];					
				}							
			}
			
			//echo '<pre>';					
			//print_r($tablaEstadosAFD);
			//echo '</pre>';	

			
			$i++;
			//para detenerse: Mientras exista un estado en $tablaEstadosAFD no marcado
			$parar = true;
			foreach($tablaEstadosAFD as $estadoAFD)
				if ($estadoAFD->marcado != 1)
					$parar = false;
		}
		
		//Comprobar si es aceptación
		foreach($tablaEstadosAFD as $estadoAFD){
			foreach($estadoAFD->conjuntoEstados as $subestado)
				if ($subestado==$estadoFinalAFN)
					$estadoAFD->aceptacion=1;		
		}
		
		
		//echo '<pre>';					
		//print_r($tablaEstadosAFD);
		//echo '</pre>';	
	


		//--------------------------------------------------------------------------------------------------------------------------------------------			
		//Impresion
		
		echo'Tabla de estados y transiciones:</br><table border="1" cellalign="center" cellpadding="10">';
		echo'<tr>
			 <td width="25%">Estado del AFN</td>
			 <td width="25%">Estado del AFD</td>';
		
		foreach($myAlfabeto as $simbolo)
			echo '<td>'.$simbolo.'</td>';
		
		echo '</tr>';
		
		
		foreach($tablaEstadosAFD as $estado){
			echo'<tr>';
						
			//Estado del AFN
			echo '<td>{';
			$cont = 0;
			foreach($estado->conjuntoEstados as $subestado){
				if ($cont==0) 
					echo $subestado;
				else
					echo ', '.$subestado;
				$cont++;
			}
			echo '}</td>';
			
			//Estado del AFD
			echo '<td>'.$estado->letra.'</td>';
			
			//Transiciones
			foreach($myAlfabeto as $simbolo)
				echo '<td>'.$estado->transiciones[$simbolo].'</td>';


			echo'</tr>';
		}	
				
		echo '</table><ul>';
		
		
		//Imprimir estados
		$enArchivo = '==== Algorimo de Subconjuntos ===='.PHP_EOL.PHP_EOL.'Estados = {';
		echo '<li>Estados = {';		
		$cont=0;
		foreach($tablaEstadosAFD as $estado){
			if ($cont==0){ 
				echo $estado->letra;
				$enArchivo = $enArchivo.$estado->letra;
			}
			else{
				echo ', '.$estado->letra;
				$enArchivo = $enArchivo.', '.$estado->letra;
			}
			$cont++;
		}
		echo '}</li>';	
		$enArchivo = $enArchivo.'}'.PHP_EOL.PHP_EOL;
		
		
		//Impimir alfabeto
		$enArchivo = $enArchivo.'Simbolos = {';
		echo '<li>Simbolos = {';
		$cont=0;
		foreach ($myAlfabeto as $simbolo) {
	  		if ($cont==0){
	  			echo $simbolo;
	  			$enArchivo = $enArchivo.$simbolo;
	  		}
	  		else{
	  			echo ', '.$simbolo;	  	
	  			$enArchivo = $enArchivo.', '.$simbolo;
	  		}
	  		$cont++;  			  				
		}
		echo '}';		
		$enArchivo = $enArchivo.'}'.PHP_EOL.PHP_EOL;
		
		//Impirmir inicio
		echo '<li>Inicio = {';		
		$enArchivo = $enArchivo.'Inicio = {';				
		$cont=0;
		foreach($tablaEstadosAFD as $estado){
			if ($estado->inicio==1)
				if ($cont==0){ 
					echo $estado->letra;
					$enArchivo = $enArchivo.$estado->letra;
				}
				else{
					echo ', '.$estado->letra;
					$enArchivo = $enArchivo.', '.$estado->letra;
				}
			$cont++;
		}
		echo '}</li>';	
		$enArchivo = $enArchivo.'}'.PHP_EOL.PHP_EOL;

		//Impirmir aceptacion
		echo '<li>Aceptacion = {';	
		$enArchivo = $enArchivo.'Aceptacion = {';							
		$cont=0;
		foreach($tablaEstadosAFD as $estado){
			if ($estado->aceptacion==1){
				if ($cont==0){ 
					echo $estado->letra;
					$enArchivo = $enArchivo.$estado->letra;
				}
				else{
					echo ', '.$estado->letra;
					$enArchivo = $enArchivo.', '.$estado->letra;					
				}
				$cont++;}
		}
		echo '}</li>';	
		$enArchivo = $enArchivo.'}'.PHP_EOL.PHP_EOL;

		//Impimir Transiciones		
		$enArchivo = $enArchivo.'Transiciones = ';						
		echo '</li><li>Transiciones = ';
		
		$cont=0;
		foreach($tablaEstadosAFD as $estado){
		
			foreach($estado->transiciones as $sim=>$transicion){
				if ($transicion!=NULL){
						if ($sim=="&"){$sim1 = '&#x03F5;'; $sim2 = 'E';} else {$sim1 = $sim; $sim2 = $sim;}
						if ($cont==0){
							echo '('.$estado->letra.', '.$sim1.', '.$transicion.')';
							  $enArchivo = $enArchivo.'('.$estado->letra.', '.$sim2.', '.$transicion.')';			
						}
						else{
							echo ' - ('.$estado->letra.', '.$sim1.', '.$transicion.')';
	  						$enArchivo = $enArchivo.' - ('.$estado->letra.', '.$sim2.', '.$transicion.')';			
	  					}
				}
				$cont++;  			  				
	
			}		
		}	
					
		echo '</li></ul>';			
		$enArchivo = $enArchivo.PHP_EOL.PHP_EOL;

		//Archivos
		unlink('archivoSubconjuntos.txt');
		if($fp=fopen('archivoSubconjuntos.txt','ab')){
		flock($fp, LOCK_EX);
		//write to the file
		fwrite($fp,$enArchivo);
		flock($fp,LOCK_UN);
		fclose($fp);
		echo "La informacion ha sido guardada en un archivo de texto <a href='archivoSubconjuntos.txt'>aca.</a>";
		}else{
		echo "Error al escribir el archivo";
		}		
		
	}
	
	//--------------------------------------------------------------------------------------------------------------------------------------------				
	//Funcion Mueve
	function mueve($conjuntoEstados,$estados,$simbolo){
		$regresar = array();
		
		foreach($estados as $estado)
			foreach($conjuntoEstados[$estado]->transiciones as $mySimbolo=>$transicion)
				if ($transicion!=NULL)
					foreach($transicion as $subtransicion)
						if (($mySimbolo == $simbolo) && (!in_array($subtransicion,$regresar)))
							$regresar[] = $subtransicion;
		return $regresar;
		//Imprimir - con fin de pruebas
		//echo '<pre>';
		//print_r($regresar);
		//echo '</pre>';						
	}
	
	
	//--------------------------------------------------------------------------------------------------------------------------------------------				
	//Funcion Cerradura Epsilon 
	function cerrE($TablaEstados,$estados){
		$return = array();
		$stEstados = new Stack;
		
		foreach($estados as $estado){
			$stEstados->push($estado);
			$return[] = $estado;
		}
		
		while (!$stEstados->is_empty()){
			$t = $stEstados->top();
			$stEstados->pop();
			foreach($TablaEstados as $estado)
				if($estado->transiciones['&'] != NULL)
					foreach($estado->transiciones['&'] as $transicion)
						if (($estado->numero+0) == $t)
							if (!in_array($transicion,$return)){
								$return[] = $transicion;
								$stEstados->push($transicion);
							}									
		}
		return $return;
		//Imprimir - con fin de pruebas
		//echo '<pre>';
		//print_r($return);
		//echo '</pre>';						

	}
								
?>